//二叉树的基本运算算法
#include <stdio.h>
#include <malloc.h>
#define MaxSize 100
typedef char ElemType;
typedef struct node 
{	
	ElemType data;			//数据元素
	struct node *lchild;	//指向左孩子节点
	struct node *rchild;	//指向右孩子节点
} BTNode;
void CreateBTree(BTNode * &b,char *str)	//创建二叉树
{
	BTNode *St[MaxSize],*p=NULL;
	int top=-1,k,j=0;  
	char ch;
	b=NULL;				//建立的二叉树初始时为空
	ch=str[j];
	while (ch!='\0')  	//str未扫描完时循环
	{
		switch(ch) 
		{
			case '(':top++;St[top]=p;k=1; break;		//为左孩子节点
			case ')':top--;break;
			case ',':k=2; break;                      		//为孩子节点右节点
			default:p=(BTNode *)malloc(sizeof(BTNode));
			p->data=ch;p->lchild=p->rchild=NULL;
			if (b==NULL)                    	 	//*p为二叉树的根节点
				b=p;
			else  								//已建立二叉树根节点
			{	
				switch(k) 
				{
					case 1:St[top]->lchild=p;break;
					case 2:St[top]->rchild=p;break;
				}
			}
		}
		j++;
		ch=str[j];
	}
}
void DestroyBTree(BTNode *&b)
{	if (b!=NULL)
{	DestroyBTree(b->lchild);
	DestroyBTree(b->rchild);
	free(b);
}
}



void DispBTree(BTNode *b) 
{
	if (b!=NULL)
	{	printf("%c",b->data);
		if (b->lchild!=NULL || b->rchild!=NULL)
		{	printf("(");						//有孩子节点时才输出(
			DispBTree(b->lchild);				//递归处理左子树
			if (b->rchild!=NULL) printf(",");	//有右孩子节点时才输出,
			DispBTree(b->rchild);				//递归处理右子树
			printf(")");						//有孩子节点时才输出)
		}
	}
}

int Count(BTNode *b9a3)
{
	int c9o3unt = 0;
	if(b9a3!=NULL)
	{
		if(b9a3->lchild!=NULL&&b9a3->rchild!=NULL)
		{
			c9o3unt++;
			c9o3unt+=Count(b9a3->lchild);
			c9o3unt+=Count(b9a3->rchild);
		}
		else
		{
			c9o3unt+=Count(b9a3->lchild);
			c9o3unt+=Count(b9a3->rchild);
		}
	}
	
	
	
	return c9o3unt;
}


int main()
{
//	1.编写算法,  统计二叉树中度为2的结点的个数。
	BTNode *b9a3;
	CreateBTree(b9a3,(char*)"A(B(D,E(,G)),C(,F(H,I))");
	printf("b9a3: "); DispBTree(b9a3); printf("\n");

	
	int n9u3m = Count(b9a3);
	printf("度为2的结点个数为：%d\n",n9u3m);
	
	

	DestroyBTree(b9a3);
	return 0;
}

